package leetcode.dichotomy.democ;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author cyt
 * @create 2020-09-24 17:50
 */
public class Tc2 {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> ret = Arrays.stream(arr).boxed().collect(Collectors.toList());
        int n = ret.size();
        if (x <= ret.get(0)) {
            return ret.subList(0, k);
        } else if (ret.get(n - 1) <= x) {
            return ret.subList(n - k, n);
        } else {
            int index = Collections.binarySearch(ret, x);
            if (index < 0) {
                index = -index - 1;
            }
            int low = Math.max(0, index - k - 1), high = Math.min(ret.size() - 1, index + k - 1);

            while (high - low > k - 1) {
                if ((x - ret.get(low)) <= (ret.get(high) - x)) {
                    high--;
                } else if ((x - ret.get(low)) > (ret.get(high) - x)) {
                    low++;
                } else {
                    System.out.println("unhandled case: " + low + " " + high);
                }
            }
            return ret.subList(low, high + 1);
        }
    }

    /**
     * 先使用二分， 得到比目标元素大一点点的元素位置。 然后以次为 根位置， 得到根位置前后k-1
     * 的位置，此时便得到了前后指针， 再按照题意使用双指针求的结果， 当前后指针中的元素值等于 k 的时候就结束。
     *
     * @param args
     */

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        List<Integer> collect = Arrays.stream(arr).boxed().distinct().collect(Collectors.toList());
        new Tc2().findClosestElements(arr, 4, 3).forEach(System.out::println);
    }
}


